1. Field of Invention
The present invention relates generally to the field of data networks. More particularly, in one exemplary aspect, the present invention is directed to a computer networking device (e.g., a router) which is adapted to allocate portions of a communications network or its available bandwidth between different uses.
2. Description of Related Technology
In a typical data network, a wired or wireless router with IP forwarding function is employed to connect networks together, such as a LAN to a WAN, in order to access the Internet or other networks. Devices in communication with the router via a LAN utilize some portion of the “bandwidth” available to that router. The amount of bandwidth utilized depends on a variety of factors, such as the size of data packets being forwarded by the router to any particular connected or distant device. Certain types of applications require significantly more bandwidth than others; e.g., streaming video or multimedia applications (e.g., watching a YouTube video) will typically consume much more bandwidth than e-mail, Internet browsing, short message or text applications.
Conventional data networks typically provide what is known as “best efforts” service to all network traffic. For example, in a TCP/IP network, “best efforts” service is the default behavior, in which network nodes drop packets indiscriminately when faced with excessive network congestion. With “best efforts” service, there is no mechanism for ensuring reliable delivery of data (i.e., no quality-of-service, or QoS).
In certain situations, such as when a device requests streaming or continuous media applications (e.g., the aforementioned YouTube video clip, or video conferencing), a fairly constant and relatively high amount of the router's bandwidth is demanded to send and/or receive the information packet stream. Some of these data also have a very high sensitivity to jitter (variability in delivery time due to, e.g., network congestion), loss and delay, and are not able to tolerate significant lapses in network performance.
It follows as well that, as the number of LAN devices increases, the demand on the available bandwidth increases. Likewise, as new applications for use in distributed networking environments are developed, the problems associated with managing network resources are intensified. For example, a network may experience unsatisfactory performance as a result of users placing too high of a load on the network, and such demands may be from uses that are inconsistent with network operator business or other objectives. Thus, solutions for managing data networks using packetized protocols such as TCP/IP become necessary to cope with the increased demands; otherwise, congestion, application unpredictability, user frustration and loss of productivity can occur.
To address these network management issues, various solutions have been employed. For example, network managers often selectively add or re-allocate bandwidth to alleviate congestion. Network operators may also employ quality of service (“QoS”) and policy-based management techniques.
As previously referenced, quality-of-service (QoS) refers generally to resource reservation and control mechanisms which guarantee a certain level of performance to a data flow in accordance with requests from the application program or Internet service provider policy. QoS can be used for example to disallow certain types of packets, to slow transmission rates, to establish distinct classes of services for certain types of packets and/or users, to mark packets with a priority value, and/or to establish a queuing system. By one or a combination of these methods, QoS systems are able to give preferential treatment to certain network traffic. See, for example, U.S. Pat. No. 7,274,700 to Jin, et al. issued Sep. 25, 2007 and entitled “Router providing differentiated quality of service (QoS) and fast internet protocol packet classifying method for the router” which discloses a router for supporting differentiated QoS, and a fast Internet protocol (IP) packet classification method performed in the router. The router hierarchically divides a memory having flow tables into a fast internal cache memory and an external typical memory. The internal cache memory stores recently searched table entries. The router preferentially searches the flow tables of the internal cache memory. Only when the internal cache memory searching fails, the flow tables of the external memory are searched. Consequently, the frequency of interactions between a packet classifier and the external memory decreases to improve the speed of packet classification. The foregoing patent is merely illustrative of a broader class of prior art dealing with mechanisms for providing or enforcing QoS policy.
As the name implies, so-called policy-based network management uses policies, or rules, to define how network resources are to be allocated. An example of a policy could be to block access or disallow packets if the IP source address of the data is included on a list of disallowed addresses. A policy-based network management resource may also be utilized in conjunction with the aforementioned QoS methods, wherein the policy-based network determines when and how the QoS techniques should be applied. See, for example, U.S. Pat. No. 7,254,628 to Koops, et al. issued Aug. 7, 2007 and entitled “Network management system with validation of policies” which discloses a network management system (NMS) including a policy manager (PM) associated with a set of policies and including distribution means for sending said policies to policy enforcement points in accordance with distribution instructions via policy decision points, characterized in that said policy manager further includes validation means for validating if said policy enforcement points can enforce said policies and correcting said distribution instructions as a function of said validation.
Further, as noted above, bandwidth allocation has to some extent been employed to address the aforementioned network management issues. For example U.S. Pat. No. 7,002,971 to Enns, et al. issued Feb. 21, 2006 and entitled “High-speed internet access system” discloses an asymmetric network system which manages bandwidth allocation and configuration of remote devices in a broadband network. A modular architecture of the system permits independent scalability of upstream and downstream capacity separately for each of the upstream and downstream physical paths. Allocation of downstream bandwidth to requesting devices is made according to bandwidth utilization by other devices, bandwidth demand by the requesting remote device, class or grade of service by the requesting remote device or bandwidth guaranteed to other remote devices. Configuration parameters remotely managed by the network include device addresses (global and local), transmission credit values, upstream channel assignment and upstream transmit power level. Further, management of device configuration profiles and bandwidth allocation occurs through control and response packets respectively generated by the network and the remote devices according to network operating software located at both ends. Control packets include poll packets that request, among other things, demand for an upstream transmission. Configuration packets instruct remote devices to assume an operational state or return status or statistical data. Response packets transmitted by the remote devices provide information to the network operations center for control purposes or to confirm the state of operation of remote devices, including channel operating statistics, errors, noise, etc. in order to remove or reallocate assigned upstream channels. Downloadable network operating software enables the network operator to upgrade remote operating software or to reconfigure the response profile of the remote devices. Account administration and usage reports are also generated. IP or ATM encapsulation, as well as forward error correction and encryption, are employed in the network.
U.S. Pat. No. 7,260,635 to Pandya, et al., issued Aug. 21, 2007 and entitled “Software, systems and methods for managing a distributed network” discloses a system and method for managing network bandwidth consumption. The system may include an agent module loadable on a networked computer and configured to aid in managing bandwidth consumption within a network. The agent module is configured to obtain an allocation of network bandwidth usable by the networked computer, and is further configured to sub-allocate such allocation among multiple bandwidth-consuming components associated with the networked computer. The system may further include multiple such agent modules loadable on plural networked computers, and a control module configured to interact with each of the agent modules to dynamically manage bandwidth usage by the networked computers.
U.S. Pat. No. 7,054,327 to Hagirahim, et al., issued May 30, 2006 and entitled “Method of providing quality of service (QOS) to voice applications in routed IP networks” discloses a simplified methodology for accomplishing traffic management in a packet based network which is achieved by allowing allocation of bandwidth based on a count of the number of endpoint connections associated with a specific service for a corresponding network device. A network device (e.g., IP router) can be configured to count the number of TCP/IP and UDP/IP connections and bandwidth usage per interface. The counting can be done by identifying the IP Addresses, Type of Service (TOS), and TCP/UDP and/or UDP/IP socket number range in the IP Header of a packet and then querying a specific communication type. When reaching the maximum allowed connections or bandwidth for a specific service, the network device (e.g., IP router) stops forwarding any new calls by means of dropping packets of new calls and informing the given endpoints to disconnect the new calls. In one exemplary embodiment of the invention, a procedure for managing traffic flowing through individual routers of a packet network includes the steps of reserving a given amount of bandwidth on interfaces of the individual routers for specific types of communications traffic, periodically querying endpoint connections based on data from a corresponding router connection table, receiving responses from the periodic querying to determine a current connection status and bandwidth allocation of said endpoints and calculating current bandwidth allocation for a specific type communications service on an interface handled by the router. The router admits additional communications traffic for a specific type of communications service if bandwidth is available.
U.S. Pat. No. 6,771,661 to Chawla, et al., issued Aug. 3, 2004 and entitled “Apparatus and methods for providing event-based data communications device configuration” discloses a system and method which enable a data communications device to be programmed to automatically and dynamically modify allocation of resources upon the occurrence of specific events or times without having to break active sessions of data communications. Resource allocations can be made by bandwidth reservations provided to a data communications device via a network policy or via individual bandwidth reservation messages. The bandwidth allocation information can specify a session of data communication and future bandwidth modification information, such as a time or event, which will cause the data communications device to modify an amount of bandwidth reserved for the specified session of data communications. In operation, a data communications device receives bandwidth allocation information indicating future bandwidth allocation modification information associated with a session of data communication. The data communications device then can determine a future event upon the occurrence of which the data communications device will modify an amount of bandwidth allocated to the session of data communication. The future event can be determined based upon the future bandwidth allocation modification information and event information such as a time signal from a clock or another event signal. The data communications device can detect the occurrence of the future event in the data communications device and in response to detecting its occurrence, can modify the amount of bandwidth allocated to the session of data communications in the data communications device. Extensions to a bandwidth reservation protocol such as the RSVP protocol are defined which allow RSVP bandwidth reservation messages to specify the future bandwidth modification information.
Example—WiFi Hotspots
In the context of now ubiquitous wireless access points (e.g., WiFi “hotspots” or “APs”), little in the way of user-based configuration control of these access points or gateways is evident in the prior art. Typically, such access points will negotiate with any entity providing the proper protocol and credentials (e.g., any WiFi station or “STA” that wishes to join an AP), and the data/communications bandwidth available to the AP (such as via a wired Ethernet or similar connection to an Internet service provider) allocated on an as-available or first-come-first served basis. Via intrinsic security mechanisms, AP administrators can lock out certain users who e.g., do not authenticate properly or provide proper credentials; however, this is generally an all-or-nothing proposition, and different types of service levels cannot be selectively provided (and dynamically altered). For example, an 802.11 AP located in a common residential or enterprise setting such as an apartment building or office may be within wireless range of a number of different STAs; it may not be desired to let all of these STAs communicate with the AP, or at least have unrestricted access or equal “stature” to one or more priority users (e.g., the owner of the AP).
Moreover, the connections or associations between the AP and one or more of the STAs may be highly transitory in nature, and therefore also highly variant from a resource allocation perspective. Significant fluctuations in the number of users and associated bandwidth requirements may occur, thereby significantly impacting non- or less-transient users, including e.g., the aforementioned “priority” users. Stated simply, there is a need for an AP owner/administrator to control the use of his or her own AP, and assure that adequate resources are available when they are needed. This need has heretofore been in effect mutually exclusive with providing access and use of the same AP by other non-priority (e.g., public) users.
A variety of different approaches to providing WiFi hotspot service are known in the prior art. For example, the “FON” Wireless Ltd. system of shared wireless networks is based on FON members (“Foneros”) who agree to share their WiFi access in return for free access to all other WiFi access points within the community. FON also sells low-cost access to non-community members. FON's La Fonera routers enable Foneros to share their home WiFi access. La Fonera routers split the WiFi signal, creating a secure private channel (i.e., for broadband Internet) and a separate channel to share with other Foneros.
Foneros comprise generally two varieties: “Linuses” and “Bills”. Linuses and Bills are registered FON users who share bandwidth with other Foneros. Alternatively, so-called “Aliens” are registered FON users who do not share their bandwidth, but who may access the FON Community such as by purchasing access passes (FON Passes). By utilizing the La Fonera WiFi Router, both Linuses and Bills can share their WiFi in exchange home and roaming WiFi privileges.
Similarly, the Netgear HSIAB-001 “Hotspot in a Box” is a system aimed at small businesses to enable them to host their own public access WiFi (Wireless) Hotspot. The system comprises a dual band wireless VPN firewall router (FWAG114) and a managed WiFi Hotspot service (i.e., “The Cloud”). Hotspot-in-a-box enables a business owner to offer wireless broadband Internet connectivity to its customers without the requirements of managing a WiFi network.
WiFi users can obtain online access with their service provider via the Cloud's WiFi network (for example BT Openzone), or alternatively use a pay-as-you-go solution to buy access time while they are at the business location. The business owner providing the hotspot earns money for the time that someone is connected (managed by The Cloud and paid directly to the business owner).
Despite the foregoing approaches, there is a salient need for a mechanism to effectively manage and control the operation of a network (including for example WiFi “hotspots” within a wireless LAN) by inter alia allocating the available resources, such as bandwidth, according to user-determined specifications or input.
Such methods and apparatus ideally should provide the network administrator with readily accessible and flexible control over their network for a variety of different operational circumstances, and according to a number of different network parameters such as type of application, geographic proximity or location (e.g., range), type of wireless air interface, etc., and should not significantly impede router or gateway performance due to e.g., latencies associated with administrative processing.
The ability to reserve resources for certain classes of users would also be highly desirable.